As data processing systems become more complex, multipliers are required to execute multiplication operations for operands with more bits in a shorter amount of time. As the number of bits in the operands increases, the number of partial products used to form a multiplication product is also increased. Correspondingly, the amount of circuitry required to implement the multiplier and the time required to execute the multiplication operation are also proportionally increased.
One method for increasing the speed with which a multiplier performs a multiplication operation implements a recoding algorithm, such as a Modified Booth's algorithm, to reduce a number of partial products generated to form the multiplication product. By using the Modified Booth's algorithm, a signed multiplication operation is accomplished using half of the previously required number of partial products. An unsigned multiplication operation generates one more partial product than the signed multiplication operation. In Modified Booth's algorithm, a multiplier operand is segmented into sections of three bits. Each one of the three-bit sections is encoded to form a set of control signals. In turn, each one of the control signals enables a logic circuit, such as a multiplexor, to perform a predetermined operation on a multiplicand operand. For the Modified Booth's algorithm, the predetermined operation may be a multiplication by either a zero, a positive or negative one, or a positive or negative two. A more detailed description of the Modified Booth's algorithm may be found in U.S. Pat. No. 4,575,812 entitled "X.times.Y Bit Array Multiplier/Accumulator Circuit" by Kloker et al. and assigned to the assignee hereof.
The Modified Booth's algorithm provides a method for performing a multiplication operation more quickly and with less logic circuitry than conventional methods. In addition to increasing the speed of the multiplication operation, multiplier circuits are also required to multiply operands which have an increased number of bits. To compensate for the increasing number of bits and still maintain a minimum amount of circuit area, iterative multiplier circuits have been developed. An iterative multiplier reuses a substantial portion of its circuitry to perform a multiplication operation. During a multiplication operation, an iterative multiplier performs a first iteration of the multiply operation and accumulates a first result. The iterative multiplier then performs one or successive iterations of the multiply operation and adds the first result to a plurality of successive results to iteratively form a product. Because each iteration of the iterative multiplication operation uses the same multiplier circuitry, the increased bit width of the operands does not substantially increase the circuit area. Therefore, when implementing a multiplier which uses both the Modified Booth's algorithm and the iterative multiplier circuit, a multiplication operation with larger operands may be performed using a minimal circuit area.
For example, during a signed multiplication operation in which the operands have word sizes which are integral powers of two bits (e.g. 8, 16, 32), The Modified Booth's algorithm typically generates a plurality of partial products, the number of which is also a power of two. This set of partial products may be efficiently summed in a symmetrical circuit layout referred to as a binary summation tree. The binary nature of the word sizes generally results in a symmetric summation tree which allows the signed multiplication operation to be performed with a significant increase in speed. However, during an unsigned multiplication operation, an extra partial product is generated. Therefore, the summation tree must be implemented in an asymmetric configuration to compensate for a number of partial products which is not a power of two. The asymmetrical circuit layout is not easily implemented in an iterative multiplier. The asymmetrical circuit detracts from both the speed performance of the signed multiplication and the circuit area required to implement a multiplier which performs unsigned multiplication operations.
Although an iterative multiplier which implements the Modified Booth's algorithm provides improvements over other conventional multipliers, a need exists for a multiplier to perform unsigned multiplication operations more efficiently. The speed at which the unsigned multiplication operation is performed should be increased without a loss of circuit area. Additionally, the number of components required to implement the unsigned multiplication operation should be minimized.